package DynamicProgramming;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class _377_CombinationSumIV {
    public int combinationSum4_0(int[] nums, int target) {
        if (target == 0) {
            return 0;
        }
        Set<Integer> num = new HashSet<>();
        int len = nums.length;
        int[] dp = new int[target + 1];
        for (int i = 0; i < len; i++) {
            num.add(nums[i]);
        }
        dp[0] = 1;
        for (int i = 0; i <= target; i++) {
            for (int j = 0; j < i; j++) {
                int sub = i - j;
                if (num.contains(sub)) {
                    dp[i] += dp[j];
                }
            }
            if (i > target) {
                break;
            }
        }
        return dp[target];
    }

    int[] nums;
    int[] dp;
    public int combinationSum4(int[] nums, int target) {
        this.dp = new int[target + 1];
        this.nums = nums;
        Arrays.fill(dp, -1);
        dp[0] = 1;
        return helper(target);
    }

    public int helper(int target) {
        if (dp[target] != -1) {
            return dp[target];
        } else {
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                if (target - nums[i] >= 0) {
                    sum += helper(target - nums[i]);
                }
            }
            dp[target] = sum;
            return sum;
        }
    }
}
